package org.apache.commons.graph.algorithms.spanning

import org.apache.commons.graph.CommonsGraph.minimumSpanningTree
import org.apache.commons.graph.Graph
import org.apache.commons.graph.SpanningTree
import org.apache.commons.graph.model.*
import org.apache.commons.graph.weight.primitive.DoubleWeightBaseOperations
import org.junit.Assert
import org.junit.Test
import kotlin.test.assertEquals

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 *
 */
class ReverseDeleteTestCase {
    @Test
    fun testEmptyGraph() {
        val input =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val tree: SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            minimumSpanningTree(input)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .applyingReverseDeleteAlgorithm(DoubleWeightBaseOperations)

        assertEquals(0, tree.order)
        assertEquals(0, tree.size)
    }

//    @Test(expected = NullPointerException::class)
//    fun testNullGraph() {
//        minimumSpanningTree(null as Graph<BaseLabeledVertex?, BaseLabeledWeightedEdge<Double?>?>?)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .applyingReverseDeleteAlgorithm(DoubleWeightBaseOperations)
//    }
//
//    @Test(expected = NullPointerException::class)
//    fun testNullMonoid() {
//        val input: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>? = null
//
//        minimumSpanningTree(input)
//            .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
//            .applyingReverseDeleteAlgorithm(null)
//    }

    /**
     * Test Graph and Reverse-Delete Algorithm
     */
    @Test
    fun testVerifyMinimumSpanningTree() {
        val input =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        val c = BaseLabeledVertex("c")

        input.addVertex(a)
        input.addVertex(b)
        input.addVertex(c)

        input.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        input.addEdge(b, BaseLabeledWeightedEdge("b <-> c", 21.0), c)
        input.addEdge(c, BaseLabeledWeightedEdge("c <-> a", 4.0), a)

        // expected
        val expected =
            MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>(
                DoubleWeightBaseOperations,
                BaseWeightedEdge()
            )

        for (vertex in input.vertices) {
            expected.addVertex(vertex)
        }

        expected.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        expected.addEdge(c, BaseLabeledWeightedEdge("c <-> a", 4.0), a)

        val actual: SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            minimumSpanningTree(input)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .applyingReverseDeleteAlgorithm(DoubleWeightBaseOperations)
        Assert.assertEquals(expected, actual)
    }

    /**
     * Test Graph and Reverse-Delete Algorithm
     */
    @Test
    fun testVerifyNotConnectGraph() {
        val input =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        val c = BaseLabeledVertex("c")

        input.addVertex(a)
        input.addVertex(b)
        input.addVertex(c)

        // expected
        val expected =
            MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>(
                DoubleWeightBaseOperations,
                BaseWeightedEdge()
            )

        for (vertex in input.vertices) {
            expected.addVertex(vertex)
        }

        val actual: SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            minimumSpanningTree(input)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .applyingReverseDeleteAlgorithm(DoubleWeightBaseOperations)
        Assert.assertEquals(expected, actual)
    }

    /**
     * Test Graph and Reverse-Delete Algorithm
     */
    @Test
    fun testVerifyNotConnectGraph2() {
        val input =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        val c = BaseLabeledVertex("c")
        val d = BaseLabeledVertex("d")
        val e = BaseLabeledVertex("e")


        input.addVertex(a)
        input.addVertex(b)
        input.addVertex(c)
        input.addVertex(d)
        input.addVertex(e)

        input.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        input.addEdge(b, BaseLabeledWeightedEdge("b <-> c", 21.0), c)
        input.addEdge(c, BaseLabeledWeightedEdge("c <-> a", 4.0), a)

        input.addEdge(d, BaseLabeledWeightedEdge("d <-> e", 4.0), e)

        // expected
        val expected =
            MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>(
                DoubleWeightBaseOperations,
                BaseWeightedEdge()
            )

        for (vertex in input.vertices) {
            expected.addVertex(vertex)
        }

        expected.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        expected.addEdge(c, BaseLabeledWeightedEdge("c <-> a", 4.0), a)

        expected.addEdge(d, BaseLabeledWeightedEdge("d <-> e", 4.0), e)

        val actual: SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            minimumSpanningTree(input)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .applyingReverseDeleteAlgorithm(DoubleWeightBaseOperations)
        Assert.assertEquals(expected, actual)
    }


    /**
     * Test Graph and Reverse-Delete Algorithm
     */
    @Test
    fun testVerifyNotConnectGraph3() {
        val input =
            UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>>()

        val a = BaseLabeledVertex("a")
        val b = BaseLabeledVertex("b")
        val c = BaseLabeledVertex("c")
        val d = BaseLabeledVertex("d")
        val e = BaseLabeledVertex("e")
        val f = BaseLabeledVertex("f")


        input.addVertex(a)
        input.addVertex(b)
        input.addVertex(c)
        input.addVertex(d)
        input.addVertex(e)
        input.addVertex(f)

        input.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        input.addEdge(b, BaseLabeledWeightedEdge("b <-> c", 21.0), c)
        input.addEdge(c, BaseLabeledWeightedEdge("c <-> a", 4.0), a)

        input.addEdge(d, BaseLabeledWeightedEdge("d <-> e", 7.0), e)
        input.addEdge(e, BaseLabeledWeightedEdge("e <-> f", 21.0), f)
        input.addEdge(f, BaseLabeledWeightedEdge("f <-> d", 4.0), d)

        // expected
        val expected =
            MutableSpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double>(
                DoubleWeightBaseOperations,
                BaseWeightedEdge()
            )

        for (vertex in input.vertices) {
            expected.addVertex(vertex)
        }

        expected.addEdge(a, BaseLabeledWeightedEdge("a <-> b", 7.0), b)
        expected.addEdge(c, BaseLabeledWeightedEdge("c <-> a", 4.0), a)

        expected.addEdge(d, BaseLabeledWeightedEdge("d <-> e", 4.0), e)
        expected.addEdge(f, BaseLabeledWeightedEdge("f <-> d", 4.0), d)

        val actual: SpanningTree<BaseLabeledVertex, BaseLabeledWeightedEdge<Double>, Double> =
            minimumSpanningTree(input)
                .whereEdgesHaveWeights(BaseWeightedEdge<Double>())
                .applyingReverseDeleteAlgorithm(DoubleWeightBaseOperations)
        Assert.assertEquals(expected, actual)
    }
}
